In software development, a source code is created in human-understandable high-level language and is converted to a machine readable execution program by using a compiler in most cases. In the source code, a matrix is sometimes used as a data structure for systematically managing a plurality of data elements. The matrix is a frequently used data structure and therefore is included in a standard library provided in a program execution environment.
The type of the matrix includes a fixed-length matrix and a variable-length matrix. A source code includes variable declaration that fixes the matrix size of the fixed-length matrix, and the fixed-length matrix does not change its size dynamically during operation. On the other hand, the variable declaration is needless to fix the matrix size of the variable-length matrix, and the variable-length matrix is able to change its size dynamically. How to manage a memory region during execution differs between the fixed-length matrix and the variable-length matrix, and thus both of the fixed-length matrix and the variable-length matrix are sometimes included in a program execution environment, a standard library, or the like.
There is proposed a compiler that converts a source code to an execution program for a distributed memory parallel computer. The proposed compiler divides a one-dimensional matrix in the source code into a plurality of partial matrices, each of which is a continuous section, in order to convert the one-dimensional matrix to a multidimensional matrix. The compiler performs automatic parallelization to the converted multidimensional matrix.
Also, there is proposed a matrix processing method that uses a multidimensional matrix structured as nesting of matrices (a data structure in which each element of the matrix of a higher level is a matrix of a lower level). At the time of compilation, the proposed matrix processing method generates an optimized code that is optimized under a premise that the matrices of the lowest level are stored in contiguous memory regions, as well as a non-optimized code that is not optimized in such a manner. At the time of execution, the non-optimized code is executed to access the matrices whose elements have been changed since initialization, and the optimized code is executed to access other matrices.
Also, there is proposed an algebra computing device that is capable of describing algebra operation between a plurality of vector variables briefly by utilizing an overload function of operator in an object-oriented programming language. The proposed algebra computing device reduces intermediate vector data generated during the algebra operation between the vector variables, and thereby reduces its overhead.
Also, there is proposed a compilation apparatus that handles a list vector that links a plurality of structure regions by a link list, as one data structure. The proposed compilation apparatus generates an execution program in which a predetermined number of structure regions are collectively stored in contiguous regions in a memory when a region allocation request is issued in a loop for the first time.
See, for example, Japanese Laid-open Patent Publication Nos. 2000-112901, 2000-222219, 2007-328692, and 2008-3882.
The variable-length matrix is able to dynamically change its matrix size after variable declaration and thus has an advantage of being used more easily than the fixed-length matrix in creating a source code. On the other hand, an execution program that includes the variable-length matrix has the next problem in execution efficiency.
The fixed-length matrix has a fixed matrix size, and thus its data elements are able to be arranged densely and contiguously in a memory, so that the compiled execution program often uses the contiguous memory regions. In contrast, the variable-length matrix has a variable matrix size, and thus all data elements are unable to be arranged densely in a memory, depending on how to use the variable-length matrix. Thus, the compiled execution program uses discontiguous memory regions in some cases. For example, a memory region corresponding to a certain row and a memory region corresponding to the next row are sometimes discontiguous in a variable-length two-dimensional matrix whose number of columns is variable. It is concerned that, when the memory regions are discontiguous, the execution efficiency becomes lower, due to decrease in cache efficiency, than when the memory region are contiguous.